#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include <queue>
#define MOD 1000000007
class Solution {
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        std::deque<int> q;
        std::vector<int> ans;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            if (!q.empty()&&q.front() <= i-k)
            {
                q.pop_front();
            }
            while (!q.empty()&&nums[q.back()]<=nums[i])
            {
                q.pop_back();
            }
            q.push_back(i);
            if (i>=k-1)
            {
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};
 